#pragma once

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <assert.h>
#include "Common.h"

// 开散列：(拉链法-链地址法-哈希桶) 原理：数组+链表

template<class T>
struct HashNode
{
	HashNode(const T& value = T())
	    : _next(nullptr)
	    , _value(value)
	{}

	HashNode<T>* _next;
	T _value;
};


// 前置声明
template<class T, class KOfV, class T2D = T2DDef<T>>
class HashBucket;


template<class T, class KOfV, class Ref, class Ptr, class T2D>
class HashBucketIterator
{
	typedef HashNode<T> Node;
	typedef HashBucketIterator<T, KOfV, Ref, Ptr, T2D> Self;

public:
	HashBucketIterator(HashBucket<T, KOfV, T2D>* ht, Node* pNode = nullptr)
		: _ht(ht)
		, _pNode(pNode)
	{}

	///////////////////////////////////
	// 具有指针类似的行为
	Ref operator*()
	{
		return _pNode->_value;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	////////////////////////////////////////
	// 移动:只支持++
	Self& operator++()
	{
		Next();
		return *this;
	}

	Self operator++(int)
	{
		Self temp(*this);
		Next();
		return temp;
	}

	//////////////////////////////////////////
	// 比较
	bool operator!=(const Self& s)const
	{
		return _pNode != s._pNode;
	}

	bool operator==(const Self& s)const
	{
		return _pNode == s._pNode;
	}

	void Next()
	{
		if (_pNode->_next)
		{
			_pNode = _pNode->_next;
		}
		else
		{
			// 计算_pNode处于那个桶中
			size_t bucketNo = _ht->HashFunc(_pNode->_value);
			for (size_t i = bucketNo + 1; i < _ht->BucketCount(); ++i)
			{
				_pNode = _ht->_table[i];
				if (_pNode)
					return;
			}

			_pNode = nullptr;
		}
	}

	Node* _pNode;
	HashBucket<T, KOfV, T2D>* _ht;
};


// T2D：将T转换为整形数字
template<class T, class KOfV, class T2D>
class HashBucket
{
	typedef HashNode<T> Node;
	friend class HashBucketIterator<T, KOfV, T&, T*, T2D>;

public:
	typedef HashBucketIterator<T, KOfV, T&, T*, T2D> iterator;

public:
	HashBucket(size_t initCapacity = 13)
		: _table(GetNextPrime(initCapacity))
		, _size(0)
	{}

	~HashBucket()
	{
		clear();
	}


	iterator begin()
	{
		for (size_t i = 0; i < _table.capacity(); ++i)
		{
			if (_table[i])
			{
				return iterator(this, _table[i]);
			}
		}

		return end();
	}

	iterator end()
	{
		return iterator(this, nullptr);
	}

	// value是唯一的
	pair<iterator, bool> InsertUnique(const T& value)
	{
		CheckCapacity();
		// 1. 通过哈希函数计算value所在的桶号
		size_t bucketNo = HashFunc(value);

		// 2. 检测value是否存在与bucketNo的桶中
		Node* cur = _table[bucketNo];
		while (cur)
		{
			if (cur->_value == value)
				return make_pair(iterator(this, cur), false);

			cur = cur->_next;
		}

		// 3. 插入新节点
		cur = new Node(value);
		cur->_next = _table[bucketNo];
		_table[bucketNo] = cur;
		++_size;
		return make_pair(iterator(this, cur), true);
	}

	pair<iterator, bool> InsertEqual(const T& value)
	{
		CheckCapacity();
		// 1. 通过哈希函数计算value所在的桶号
		size_t bucketNo = HashFunc(value);

		// 2. 直接插入
		Node* newNode = new Node(value);
		newNode->_next = _table[bucketNo];
		_table[bucketNo] = newNode;
		++_size;
		return make_pair(iterator(this, cur), true);
	}

	size_t EraseEqual(const T& value)
	{
		// 1. 通过哈希函数计算value所在的桶号
		size_t bucketNo = HashFunc(value);

		// 2. 在bucketNo的桶中删除所有值为value的节点
		Node* cur = _table[bucketNo];
		Node* prev = nullptr;
		size_t oldsize = _size;
		KOfV kofv;
		while (cur)
		{
			if (kofv(cur->_value) == kofv(value))
			{
				if (nullptr == prev)
				{
					_table[bucketNo] = cur->_next;
					delete cur;
					cur = _table[bucketNo];
				}
				else
				{
					// prev--->cur--->curNext
					prev->_next = cur->_next;
					delete cur;
					cur = prev->_next;
				}

				--_size;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}

		return oldsize - _size;
	}


	size_t EraseUnique(const T& value)
	{
		// 1. 通过哈希函数计算value所在的桶号
		size_t bucketNo = HashFunc(value);

		// 2. 再在bucketNo桶中插入是否存在value的元素
		//    存在则删除
		Node* cur = _table[bucketNo];
		Node* prev = nullptr;
		KOfV kofv;
		while (cur)
		{
			if (kofv(cur->_value) == kofv(value))
			{
				if (nullptr == prev)
					_table[bucketNo] = cur->_next;
				else
					prev->_next = cur->_next;

				delete cur;
				--_size;
				return 1;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}

		return 0;
	}

	iterator Find(const T& value)
	{
		// 1. 通过哈希函数计算value所在的桶号
		size_t bucketNo = HashFunc(value);

		// 2. 检测value是否存在
		Node* cur = _table[bucketNo];
		KOfV kofv;
		while (cur)
		{
			if (kofv(value) == kofv(cur->_value))
				return iterator(this, cur);

			cur = cur->_next;
		}

		return end();
	}

	size_t size()const
	{
		return _size;
	}

	bool Empty()const
	{
		return 0 == _size;
	}

	void swap(HashBucket<T, T2D>& ht)
	{
		_table.swap(ht._table);
		std::swap(_size, ht._size);
	}

	void clear()
	{
		for (size_t i = 0; i < BucketCount(); ++i)
		{
			Node* cur = _table[i];
			while (cur)
			{
				_table[i] = cur->_next;
				delete cur;
				cur = _table[i];
			}
		}

		_size = 0;
	}

	size_t BucketCount()const
	{
		return _table.capacity();
	}

	size_t BucketSize(size_t bucketNo)const
	{
		assert(bucketNo < BucketCount());
		Node* cur = _table[bucketNo];
		size_t count = 0;
		while (cur)
		{
			count++;
			cur = cur->_next;
		}

		return count;
	}

	size_t Bucket(const T& value)const
	{
		return HashFunc(value);
	}

	////////////////////////////////////////////
	// 辅助方法
	void PrintHashBucket()const
	{
		for (size_t bucketNo = 0; bucketNo < _table.capacity(); ++bucketNo)
		{
			Node* cur = _table[bucketNo];
			cout << "_table[" << bucketNo << "]:";
			
			while (cur)
			{
				cout << cur->_value<<"--->";
				cur = cur->_next;
			}
			cout << "NULL" << endl;
		}

		cout << "===============================" << endl;
	}
private:

	size_t HashFunc(const T& value)const
	{
		T2D t2D;
		return t2D(KOfV()(value)) % _table.capacity();
	}

	size_t HashFunc(const T& value, size_t capacity)const
	{
		T2D t2D;
		return t2D(KOfV()(value)) % capacity;
	}

	void CheckCapacity()
	{
#if 0
		if (_size == _table.capacity())
		{
			// HashBucket<T, T2D> newHT(GetNextPrime(_size));
			HashBucket<T, T2D> newHT(_size*2);
			for (size_t i = 0; i < _table.capacity(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					newHT.InsertEqual(cur->_value);
					cur = cur->_next;
				}
			}

			this->swap(newHT);
		}
#endif
		if (_size == _table.capacity())
		{
			vector<Node*> newTab(GetNextPrime(_table.capacity()));

			// 依次拿到_table中的每个桶
			for (size_t i = 0; i < _table.capacity(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					// 将cur从_table的第i个桶中移除
					_table[i] = cur->_next;

					// 将cur往newTab中插入
					// 1. 获取桶号
					size_t bucketNo = HashFunc(cur->_value, newTab.capacity());

					// 2.插入新节点
					cur->_next = newTab[bucketNo];
					newTab[bucketNo] = cur;

					// 3. 获取_table中第i个桶的下一个节点
					cur = _table[i];
				}
			}

			_table.swap(newTab);
		}
	}

private:
	vector<Node*> _table;
	size_t _size;
};


#if 0
void TestHashBucket()
{
	HashBucket<int> hb(8);
	hb.InsertUnique(44);
	hb.InsertUnique(12);
	hb.InsertUnique(78);
	hb.InsertUnique(54);
	hb.InsertUnique(11);
	hb.InsertUnique(34);
	hb.InsertUnique(67);
	hb.InsertUnique(90);
	hb.InsertUnique(55);

	cout << hb.size() << endl;
	hb.PrintHashBucket();

	hb.EraseUnique(34);
	hb.EraseUnique(44);
	hb.PrintHashBucket();

	cout << "桶的个数：" << hb.BucketCount() << endl;
	for (size_t i = 0; i < hb.BucketCount(); ++i)
	{
		cout << i << "桶：" << hb.BucketSize(i) << endl;
	}
	cout << hb.Bucket(55) << endl;

	hb.PrintHashBucket();
	cout << "================" << endl;

	for (auto e : hb)
		cout << e << " ";
	cout << endl;

	auto it = hb.begin();
	while (it != hb.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

#include <string>

void TestHashBucketString()
{
	HashBucket<string, Str2D> ht;
	ht.InsertUnique("apple");
	ht.InsertUnique("orange");
	ht.InsertUnique("grape");
}
#endif